from typing import *
from heapq import heappush, heappop
from math import inf


class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        nexts = [[] for _ in range(n)]
        times = [[0] * n for _ in range(n)]
        for u, v, time in roads:
            nexts[u].append(v)
            nexts[v].append(u)
            times[u][v] = time
            times[v][u] = time
        ans = [0] * n
        mnCosts = [inf] * n
        ans[0], mnCosts[0] = 1, 0
        q = [(0, 0)]
        mod = 1000000007
        while q:
            cost, cur = heappop(q)
            for next in nexts[cur]:
                if ans[next] == 0 or cost + times[cur][next] <= mnCosts[next]:
                    if ans[next] == 0 or cost + times[cur][next] < mnCosts[next]:
                        mnCosts[next] = cost + times[cur][next]
                        heappush(q, (mnCosts[next], next))
                        ans[next] = 0
                    ans[next] += ans[cur]
                    ans[next] %= mod
        return ans[n - 1]


s = Solution()
print(
    s.countPaths(
        n=7,
        roads=[
            [0, 6, 7],
            [0, 1, 2],
            [1, 2, 3],
            [1, 3, 3],
            [6, 3, 3],
            [3, 5, 1],
            [6, 5, 1],
            [2, 5, 1],
            [0, 4, 5],
            [4, 6, 2],
        ],
    )
)
